In multicast/broadcast applications, data are transmitted from a server to multiple receivers over wired and/or wireless networks. A multicast system as used herein is a system in which a server transmits the same data to multiple receivers simultaneously, where the receivers form a subset of all the receivers up to and including all of the receivers. A broadcast system is a system in which a server transmits the same data to all of the receivers simultaneously. That is, a multicast system by definition can include a broadcast system.
The popularity of voice and video applications over mobile computing devices has raised concerns regarding the performance of medium access control (MAC) protocols, which are responsible for allocating shared medium resources to multiple communicating stations and resolving collisions that occur when two or more stations access the medium simultaneously. In the current IEEE 802.11 wireless LANs, the distributed coordination function (DCF) of the MAC protocol layer uses a binary exponential back-off (BEB) algorithm for fundamental channel access. The BEB algorithm mitigates the issue of network collisions by randomizing the timing of medium access among stations that share the communication medium. The timing of channel access in the BEB algorithm is randomized by setting the slot counter to a random integer selected from contention window [0, CW] in each back-off cycle, and CW doubles upon failed data transmissions in last back-off cycle. Here a back-off cycle is a procedure where the back-off slot counter decrements down from an initial maximal value to zero. The simplicity and good performance of BEB contribute to the popularity of IEEE 802.11 DCF/EDCA.
However, as demonstrated by both practical experience and theoretical analysis, the BEB algorithm has some deficiencies. First, the collision probability for a transmission attempt increases exponentially with the number of active stations in the network. Second, the medium access delay cannot be bounded and the jitter is variable, which may not be suitable for multimedia applications.
Some concepts/terms that may benefit the understanding of the present invention are provided. A frame is a unit of data. That is, data can be packaged in packets or frames or any other convenient format. As used herein a frame is used to indicate data packaged in a format for transmission. A back-off round/stage/cycle is a procedure in which the back-off slot counter counts down from an initial value (maximum) to zero. When the counter reaches zero, a new transmission is attempted. One frame transmission may involve multiple back-off rounds/stages (because of unsuccessful transmission attempts). As used herein a time slot represents a continuous time period during which the back-off slot counter is frozen. It may refer to either a fixed time period (usually several microseconds) sufficient for the physical layer to perform the carrier sensing once, or a varying time period (usually between hundreds of microseconds to several milliseconds, depending on the length of the packet and physical data rate) when a frame is being transmitted over the shared medium. In a network with shared medium, each station freezes or decreases its back-off slot counter based on the resulting status of the physical or virtual carrier sensing of the medium. Hence, because of the shared nature of the medium, the slot count changes are aligned among the stations. The time slot can be used as a basic time unit to make the entire procedure discrete. Positive integers n=1, 2, 3, . . . , N are used to indicate the 1st, 2nd, 3rd, . . . , Nth time slot, and is used to indicate the status of the shared medium at the nth slot, for example, In=1 when busy and In=0 otherwise. The back-off slot count of station i at the nth time slot is denoted as sloti(n).
In Application Serial Number PCT/US09/01179, a deterministic back-off (DEB) method was described to reduce or avoid collisions. In the DEB method, transmission were deterministically scheduled in time slots
In Application Serial Number PCT/US09/001,855, a relaxed deterministic back-off (R-DEB) method was described to overcome issues such as backward compatibility and dependability that are inherent in the deterministic back-off (DEB) method. The R-DEB method selects the back-off slot count in as deterministic a way as possible to reduce or avoid network collisions. The R-DEB method also introduces randomness to this procedure to preserve the flexibility and easy deployment feature of the conventional random back-off methods such as the BEB (binary exponential back-off) method. Hence, the R-DEB method made a compromise between the network efficiency and flexibility, and can be viewed as a combination of the DEB algorithm and BEB algorithm. The initial motivation of the R-DEB algorithm was to adapt the deterministic back-off for video transport systems while maintaining backward compatibility with the previous standards.
The R-DEB operates as follows. A back-off round starts when a station resets its back-off slot count slot(n) to the fixed number M (note that here n is a variable on the timeline). Once it is determined by the physical carrier sensing procedure that the sharing medium is idle for a time slot, the station decreases its back-off slot count by one. If this new slot count satisfies the transmission triggering condition (that is, the new slot count equals one of the elements of the triggering set QT, e.g., slot(n)=k). The node (station, client device, mobile terminal, mobile device) will get an opportunity to initiate a data transmission (hence “triggering a transmission”). If no frame is to be sent at this time, the node forgoes the opportunity and continues decreasing its slot count. The result of the data transmission determines whether or not the element k should further remain in the triggering set: if there was a successful transmission then this triggering element remain in the triggering set; if there was an unsuccessful data transmission then, with a probability p, a triggering element substitution procedure will be initiated that replaces the old element k with a new one k′ from the interval [0, M]. The R-DEB method included a method and apparatus for selecting an element from the interval [0, M−1] for inclusion in the triggering set QT to reduce network collisions. It should be noted that a station can be a computer, laptop, personal digital assistant (PDA), dual mode smart phone or any other device that can be mobile.
The notion of resource reservation is a well known and widely used in time division multiple access (TDMA) schemes to achieve high throughput and a certain level of quality of service (QoS) provisioning for asynchronous transfer mode (ATM) networks. In a typical TDMA reservation (R-TDMA) solution, the radio resource is organized into superframes with each superframe divided into multiple time slots of equal length, and a station can subscribe one or more time slots in each superframe as its reserved radio resource by a reservation request. As used herein a node (client, mobile station, mobile device, mobile terminal, station, laptop, computer, personal digital assistant (PDA), dual mode smart phone, . . . ) are all terms that can be used to indicate an end device in a wireless local area network (WLAN). A station can have collision-free channel access in these reserved time slots, thus QoS can be readily achieved. In another flexible version of R-TDMA, reservation ALOHA (R-ALOHA), the radio resource is automatically reserved by tracking the results of data transmission in the previous superframe. A successful transmission in a given time slot in the previous superframe results in a reservation of the same slot for the sender (transmitter) in subsequent superframes. FIG. 1(a) illustrates how the reservation is achieved by R-ALOHA among three stations A, B and C. Station A successfully obtains reserved slot l in the first superframe while B and C obtain their reserved slots at the second superframe because stations B and C collide with each other in the first superframe. Simulation results show that R-ALOHA achieves less delay at significantly higher channel utilization than slotted ALOHA.
The beauty of R-AHOHA lies in that, it achieves resource reservation automatically without the involvement of a central coordinator as conventional TDMA solutions usually do. The present invention borrows the idea of R-ALOHA and applies it to carrier sense multiple access (CSMA) based wireless networks. More specifically, the present invention seeks to incorporate the R-ALOHA into distributed coordination function (DCF)/enhanced distributed channel access (EDCA) to improve the QoS performance for content delivery over IEEE 802.11 networks in home environments. The challenge is how to achieve resource reservation in the context of CSMA environments.
Resource reservations in R-ALOHA are possible because of two basic features in a TDMA network, periodicity and synchronization. Periodicity means that each superframe has the same number of equal-length time slots so that a station can easily identify a time slot that it wants to use again in the current superframe. Synchronization makes time slot identification possible because the time slot is exactly the same slot the station used in the previous frame. In fact, as long as a network possesses the aforementioned two features, then resource reservation can be achieved following a similar approach as R-ALOHA.
Now the problem that remains is to determine whether or not a CSMA network possesses the two features—synchronization and periodicity. Generally, a CSMA network cannot be synchronized because of the presence of hidden terminals in multi-hop networks. However, considering a single-hop network where all stations share the same medium and assuming perfect carrier sensing, synchronization can be achieved. Synchronization in a CSMA network means that the back-off slot counters of stations in the network decrement or freeze simultaneously upon the same network event (transmitting or idle) for a time slot. The term “time slot” in CSMA context has a different meaning from that used in TDMA context. It is defined as a continuous time period during which the back-off slot counter freezes. It may last a very short time period (usually several microseconds), sufficient for the physical layer to perform carrier sensing once, or a long time period (usually from hundreds of microseconds to several milliseconds, depending on the frame size and physical data rate) sufficient to complete a frame exchange sequence. Thus the duration of a time slot in a CSMA network varies over time.
Typically, for station A and B that share the same medium, the channel state transition sequence learned by each station should be the same because of the broadcast property of wireless channels. More generally, if not considering hidden terminals, all stations sharing the medium should maintain the same sequence that reflects the utilization history of the medium. This sharing property builds the notion of synchronization of back-off slot counters among stations in the same collision domain.
To achieve periodicity in CSMA networks, deterministic selection of values for the back-off slot counter is introduced in the back-off procedure when a successful transmission occurred in last back-off cycle. Here a back-off cycle is a period of time when the back-off slot counter decrements from the initial value to zero. By deterministic selection, a station's time slot counter is reset to a common deterministic value shared by all stations in the network. This common value defines the periodicity of CSMA network (in terms of time slots).